/**
 * @projectName leetode
 * @package cn.leetcode
 * @className cn.leetcode.t105
 * @copyright Copyright 2020 Thunisoft, Inc All rights reserved.
 */
package cn.leetcode;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * t105
 * @description
 * @author fei
 * @date 2025/9/11 16:11
 * @version 1.0
 */
/*
给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。



示例 1:


输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]
示例 2:

输入: preorder = [-1], inorder = [-1]
输出: [-1]
 */
public class t105 {
//    public TreeNode buildTree(int[] preorder, int[] inorder) {
//        int n = preorder.length;
//        if (n == 0){
//            return null;
//        }
//        int leftSize = getRootIndex(inorder, preorder[0]);
//        int[] in1 = Arrays.copyOfRange(inorder,0, leftSize);
//        int[] in2 = Arrays.copyOfRange(inorder, leftSize+1, n);
//        int[] pre1 = Arrays.copyOfRange(preorder, 1, leftSize+1);
//        int[] pre2 = Arrays.copyOfRange(preorder, leftSize+1, n);
//
//        TreeNode left = buildTree(pre1, in1);
//        TreeNode right = buildTree(pre2, in2);
//        return new TreeNode(preorder[0], left, right);
//    }
//
//    public int getRootIndex(int[] inorder, int rootVal) {
//        for (int i = 0; ; i++) {
//            if (inorder[i] == rootVal) {
//                return i;
//            }
//        }
//    }

    public TreeNode buildTree(int[] preorder, int[] inorder){
        int n = preorder.length;
        Map<Integer, Integer> index = new HashMap<>();
        for (int i = 0; i < n; i++) {
            index.put(inorder[i], i);
        }
        return dfs(0,n,inorder,0,n,preorder,index);
    }

    public TreeNode dfs(int inL, int inR, int[] inorder, int preL, int preR, int[] preorder, Map<Integer, Integer> index){
        if (preL == preR){
            return null;
        }
        int leftSize = index.get(preorder[preL])-inL;
        TreeNode left = dfs(inL,inL+leftSize,inorder,preL+1,preL+1+leftSize,preorder,index);
        TreeNode right = dfs(inL+leftSize+1,inR,inorder,preL+1+leftSize,preR,preorder,index);
        return new TreeNode(preorder[preL],left,right);
    }
}
